/**
 *  @file IsSubsequence.c
 *  @desc 判断一个双向链表是否是另一个链表的连续子序列（子链表）
 *        并包含链表的基本操作如插入、删除、打印等
 *  @author WangBlue(wangjiping596@gmail.com)
 *  @date 2025-08-01 16:06
 *  @version 1.0
 */

#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>

// ------------------------- 数据结构定义 -------------------------

/**
 * @brief 双向链表结点定义
 */
typedef struct node {
    int data;               ///< 数据域
    struct node *next;      ///< 指向下一个结点
    struct node *pre;       ///< 指向上一个结点
} node, *link;

// ------------------------- 链表基础操作 -------------------------

/**
 * @brief 创建一个新的结点，初始化数据域并返回指针
 * @param value 结点的值
 * @return 成功返回结点指针，失败返回 NULL
 */
link createNode(int value) {
    link newNode = (link) malloc(sizeof(node));
    if (newNode == NULL) return NULL;
    newNode->next = NULL;
    newNode->pre  = NULL;
    newNode->data = value;
    return newNode;
}

/**
 * @brief 初始化链表，仅创建一个头结点
 * @param head 指向头指针的指针
 */
void initNode(link *head) {
    link newNode = createNode(0);  // 头结点数据域无实际意义
    if (newNode == NULL) return;
    *head = newNode;
}

/**
 * @brief 打印链表所有元素（跳过头结点）
 * @param head 链表头指针
 */
void printList(link head) {
    if (head == NULL || head->next == NULL) return;
    link cur = head->next;
    while (cur) {
        printf("value is %d\n", cur->data);
        cur = cur->next;
    }
    printf("\n");
}

// ------------------------- 插入操作 -------------------------

/**
 * @brief 头插法插入元素
 * @param head 链表头指针
 * @param value 要插入的值
 */
void istHead(link head, int value) {
    link newNode = createNode(value);
    if (newNode == NULL) return;

    newNode->pre = head;
    newNode->next = head->next;
    if (head->next != NULL) {
        head->next->pre = newNode;
    }
    head->next = newNode;
}

/**
 * @brief 尾插法插入元素
 * @param head 链表头指针
 * @param value 要插入的值
 */
void istTail(link head, int value) {
    link newNode = createNode(value);
    if (newNode == NULL) return;

    link cur = head;
    while (cur->next != NULL) {
        cur = cur->next;
    }
    newNode->pre = cur;
    cur->next = newNode;
}

/**
 * @brief 在第 pos 个位置（从1开始）插入值
 * @param head 链表头指针
 * @param value 要插入的值
 * @param pos 插入的位置（1 表示在第一个元素前插入）
 * @return 插入成功返回 true，失败返回 false
 */
bool istByPos(link head, int value, int pos) {
    if (pos < 1) return false;

    link newNode = createNode(value);
    if (newNode == NULL) return false;

    link cur = head;
    int idx = 0;

    while (cur && idx < pos - 1) {
        cur = cur->next;
        idx++;
    }

    if (cur == NULL) return false;

    newNode->next = cur->next;
    newNode->pre = cur;

    if (cur->next != NULL) {
        cur->next->pre = newNode;
    }
    cur->next = newNode;

    return true;
}

// ------------------------- 删除操作 -------------------------

/**
 * @brief 删除链表中第 pos 个位置的元素
 * @param head 链表头指针
 * @param pos 要删除的位置（从 1 开始）
 * @return 删除成功返回 true，失败返回 false
 */
bool delByPos(link head, int pos) {
    if (head == NULL || head->next == NULL) return false;
    if (pos < 1) return false;

    link cur = head->next;
    int idx = 1;

    while (cur && idx < pos) {
        cur = cur->next;
        idx++;
    }

    if (cur == NULL) return false;

    cur->pre->next = cur->next;
    if (cur->next != NULL) {
        cur->next->pre = cur->pre;
    }

    free(cur);
    return true;
}

// ------------------------- 子序列判断 -------------------------

/**
 * @brief 判断链表 lb 是否是链表 la 的连续子序列（子链表）
 * @param la 主链表（长）
 * @param lb 子链表（短）
 * @return 是子序列返回 true，否则返回 false
 */
bool isSequence(link la, link lb) {
    if (la == NULL || la->next == NULL) return false;
    if (lb == NULL || lb->next == NULL) return false;

    link pa = la->next;

    while (pa) {
        link pb = lb->next;
        link paa = pa;

        // 同时向后比对
        while (pb && paa && pb->data == paa->data) {
            pb = pb->next;
            paa = paa->next;
        }

        // 如果子链表已经走完，说明匹配成功
        if (pb == NULL) {
            return true;
        }

        pa = pa->next;
    }

    return false;
}




// ------------------------- 主函数测试 -------------------------

int main() {
    // 创建主链表 head: 1 → 2 → 3 → 4
    link head;
    initNode(&head);
    istTail(head, 1);
    istTail(head, 2);
    istTail(head, 3);
    istByPos(head, 4, 4);  // 插入到第4位
    istByPos(head, 6, 6);  // 插入到第6位（非法，链表长度不足，不影响）
    delByPos(head, 6);     // 删除第6位（非法，忽略）
    printList(head);

    // 创建子链表 head1: 2 → 3
    link head1;
    initNode(&head1);
    istTail(head1, 2);
    istTail(head1, 3);

    // 判断 head1 是否为 head 的子链表
    bool sign = isSequence(head, head1);
    if (sign) {
        printf("head1 is a subsequence of head\n");
        exit(EXIT_SUCCESS);
    } else {
        printf("head1 is NOT a subsequence of head\n");
        exit(EXIT_FAILURE);
    }
}
